/*
 * Programacao concorrente
 * Grupo-03a
 * Brenno Candido					7696500 
 * Jose Victor Uliana Martins		7656620
 * Maria Fernanda Garbim Avelino 	7277562
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 1001 // numero maximo de vertices

// Representa um peso infinito pois o
// maior peso e 100000
const int INF = 1000000;

// Matriz de adjacencia para representar o grafo
int G[N][N];

/*
 * Dado uma Matriz de adjacencia, essa funcao retorna o um vetor
 * com as menores distancias de um vertice de origem passado.
 * Argumentos:
 * 	G: matriz de adjacencia - grafo
 * 	orig: vertice de origem para os menores caminhos
 * 	n: numero de vertices do grafo
 */
int* dijkstra(int G[N][N], int orig, int n) {
	int *visited, *dist; // visited sao os vertices visitados e dist é a menos distancia ate um vetice
	int count, node;
	int i;
	
	// alocacao do vetor de vertices visitados
	visited = (int*)malloc((n+1)*sizeof(int));
	if(!visited) {
		fprintf(stderr, "error during allocation of visited array\n");
		return NULL;
	}
	dist = (int*)malloc((n+1)*sizeof(int));
	if(!dist) {
		fprintf(stderr, "error during allocation of distance array\n");
		return NULL;
	}
	
	// inicializa o vetor visitados com 0 (não visitado) e o vetor
	// de distancia com uma distancia infitita
	for(i=0; i<=n; i++) {
		visited[i] = 0; // marca como nao visitado
		dist[i] = INF; // distancia infinita
	}
	
	dist[orig] = 0; // distancia do vertice origem ate o vertice origem e zero
	node = orig; // no inicial para buscar as menores distancias

	// para todos os vertices
	for(count = n; count>0; count--) {
		
		// busca o node com com menor distancia
		for(i=1; i<=n; i++) {
			// se node nao foi visitado e tem menor distancia que a distancia do node escolhido
			if(!visited[i] && (node == -1 || (dist[i] < dist[node] && dist[i] != 0)))
				node = i;
		}
		visited[node] = 1; // marca como visitado

		// atualiza as distancias do vetor dist para cada vertice
		for(i=1; i<=n; i++) {
			if(dist[i] > dist[node]+G[node][i] && G[node][i] != 0) {
				dist[i] = dist[node]+G[node][i];
			}
		}
		// insere -1 em node para nova busca por melhor node
		node = -1;
	}

	// retorna vetor com as menores distancias a partir do vertice orig
	return dist;
}

/*
 * Retorna o maior valor pertencente ao vetor v de tamanho n
 * Argumentos:
 * 	v: vetor de inteiros
 * 	n: tamanho do vetor v
 */
int max(int* v, int n) {
	int i, max = -1;

	for(i=1; i<=n; i++) {
		if(v[i] > max && v[i] != INF) {
			max = v[i];
		}
	}
	return max;
}

/*
 * Retorna o menor valor pertencente ao vetor v de tamanho n
 * Argumentos:
 * 	v: vetor de inteiros
 * 	n: tamanho do vetor v
 */
int min(int* v, int n) {
	int i, min = INF;

	for(i=1; i<=n; i++) {
		if(v[i] < min) {
			min = v[i];
		}
	}
	return min;
}

int main(int argc, char* argv[]) {
	int MAX[N];
	int n, m;
	int a, b, w;
	int i, j;
	
	// le entrada:
	// n - numero de vertices
	// m - numero de arestas
	scanf(" %d %d", &n, &m);

	// inicializa matriz com 0
	memset(G, 0, sizeof(G[0][0])*n*n);

	// inicializa os pesos dos entre os vertices
	for(i=0; i<=m; i++) {
		scanf(" %d %d %d", &a, &b, &w);
		G[a][b] = w;
		G[b][a] = w;
	}

	// para todos os vertices...
	for(i=1; i<=n; i++) {
		// MAX[i] recebe a maior distancia obitida pelo vetor retornado
		// da funcao dijkstra para o vertice i
		MAX[i] = max(dijkstra(G, i, n), n);
	}

	// mostra a menor distancia dentro das menores distancias com a funcao min
	printf("%d\n", min(MAX, n));

	return 0;
}
